// @algorithm @lc id=877 lang=cpp 
// @title shortest-path-visiting-all-nodes


#define print(...)
// test([[1,2,3],[0],[0],[0]])=4
// test([[1],[0,2,4],[1,3,4],[2],[1,2]])=4
// @test([[2],[2,8],[0,1,3,4],[2],[2],[8,6],[5],[8],[1,5,7]])=11
#define PNT(st)     (((st)>>16)&0xFFFF)
#define VIA(st)    ((st)&0xFFFF)
#define ST(pt,path) (((pt)<<16) | (path))
using state_t = uint32_t;
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        const int n = (int)graph.size();
        if(1>=n) return 0;
        print("-------------\ngraph=\n", Mat(graph))
        unordered_set<state_t> passed;
        list<pair<state_t,int>> q;
        for(int i=0; i<n; i++){
            auto st = ST(i, 1<<i);
            passed.insert(st);
            q.emplace_back(st, 0);
        }

        while(!q.empty()){
            auto [st, dist] = q.front();
            print("\n", hex, st, " ", dist, "|", dist+1, " ")
            dist++;
            q.pop_front();
            for(auto adj : graph[PNT(st)]){
                auto next = ST(adj, VIA(st)|(1<<adj));
                if(passed.count(next)) continue;
                q.emplace_back(next, dist);
                passed.insert(next);
                print(hex, next, " ")
                if(VIA(next) == (1<<n)-1) return dist;
            }
        }
        return 0;
    }
};